package org.example.leetcode.addon.lc100;

import org.example.util.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue1.offer(p);
        queue2.offer(q);

        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode n1 = queue1.poll();
            TreeNode n2 = queue2.poll();
            if (n1.val != n2.val) {
                return false;
            }

            TreeNode l1 = n1.left;
            TreeNode r1 = n1.right;
            TreeNode l2 = n2.left;
            TreeNode r2 = n2.right;

            if (l1 == null && l2 != null) {
                return false;
            }
            if (l1 != null && l2 == null) {
                return false;
            }
            if (r1 == null && r2 != null) {
                return false;
            }
            if (r1 != null && r2 == null) {
                return false;
            }

            if (l1 != null) {
                queue1.offer(l1);
            }
            if (r1 != null) {
                queue1.offer(r1);
            }
            if (l2 != null) {
                queue2.offer(l2);
            }
            if (r2 != null) {
                queue2.offer(r2);
            }
        }

        return true;
    }
}
